package LeetCode;

/**
 * @Author: Dijah
 * @Date: 2023/1/17 16:16
 * @Desc: 解数独
 */
public class code37_solveSudoku {

    public static void solveSudoku(char[][] board){

        //回溯算法
        int i = board.length - 1;//行
        int j = board[0].length - 1;// 列
        backtrack(board,0,0);
    }

    public static boolean backtrack(char[][] board,int i,int j){
        int M = 9;
        int N = 9;
        //穷举最到后一列的话就换到下一行重新开始
            if(j == N){
            return backtrack(board,i + 1,0);
        }
            if(i == M){
            return true;
        }
        //如果该位置已经被预设数字.空白格用 '.' 表示。
            if(board[i][j] != '.'){
            return backtrack(board,i,j+1);
        }
        //开始填入数字
        for(char ch = '1'; ch <= '9'; ch++){
            //判断填入该位置的数字是否合法
            if(!isValid(board,i,j,ch)){
                continue;
            }
            //如果合法，直接将数字填到当前的位置，
            //做选择
            board[i][j] = ch;
            //进行下一列的调用，穷举下一个
            if(backtrack(board,i,j+1)){
                return true;
            }
            //撤销选择
            board[i][j] = '.';
        }
        return false;
}


    public static boolean isValid(char[][] board,int r,int c,char n){
        //判断填入的数字是否合法
        for(int i = 0; i < 9; i++){
            //判断行是否合法
            if(board[r][i] == n){
                return false;
            }
            //判断列是否合法
            if(board[i][c] == n){
                return false;
            }
            //判断 3 x 3 的方格是否合法
            if(board[(r/3) * 3 + i/3][(c/3) * 3 + i % 3] == n){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char [][] board = {
                {'5','3','.','.','7','.','.','.','.'},
                {'6','.','.','1','9','5','.','.','.'},
                {'.','9','8','.','.','.','.','6','.'},
                {'8','.','.','.','6','.','.','.','3'},
                {'4','.','.','8','.','3','.','.','1'},
                {'7','.','.','.','2','.','.','.','6'},
                {'.','6','.','.','.','.','2','8','.'},
                {'.','.','.','4','1','9','.','.','5'},
                {'.','.','.','.','8','.','.','7','9'}
        };
        solveSudoku(board);
    }
}
